import java.util.TreeMap;

public class Solution {

    private class Node{
        public boolean isWord;
        public TreeMap<Character,Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            this.next = new TreeMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private int size;
    private Node root;

    public Solution(){
        size = 0;
        root = new Node();
    }
    //获取Trie中存储的单词数量
    public int getSize(){
        return size;
    }

    //向Trie中添加一个新的单词  非递归
//    public void add(String word){
//        Node cur = root;
//        for(int i=0;i<word.length();i++){
//            char c = word.charAt(i);
//            if(cur.next.get(c) == null){
//                cur.next.put(c,new Node());
//            }
//            cur = cur.next.get(c);
//        }
//
//        if(!cur.isWord){
//            cur.isWord = true;
//            size ++;
//        }
//    }

    //向Trie中添加一个新的单词  递归
    public void insert(String word){
        insert(root,0,word);
    }

    private void insert(Node node,int index,String word){
        if(index >= word.length()){
            return;
        }
        char c = word.charAt(index);
        if(node.next.get(c) == null){
            node.next.put(c,new Node());
        }
        insert(node.next.get(c),index+1,word);
        if(index == word.length() - 1){
            Node cur = node.next.get(c);
            if(!cur.isWord){
                cur.isWord = true;
                size ++;
            }
        }
//        System.out.println(node.isWord);
    }

    //查询单词是否在Trie中
//    public boolean contains(String word){
//        Node cur = root;
//        for(int i=0;i<word.length();i++){
//            char c = word.charAt(i);
//            if(cur.next.get(c) == null){
//                return false;
//            }
//            cur = cur.next.get(c);
//        }
//        return cur.isWord;
//    }

    public boolean contains(String word){
        return contains(root,0,word);

    }

    private boolean contains(Node node,int index,String word){
        char c = word.charAt(index);
        boolean result = false;
        if(node.next.get(c) == null){
            return false;
        }else {
            if(index != word.length() -1){
                result = contains(node.next.get(c),index+1,word);
            }else {
                Node cur = node.next.get(c);
                return result = cur.isWord;
            }
        }
        return result;
    }

    //查询是否在Trie中有单词以prefix为前缀
    public boolean isPrefix(String prefix){
        Node cur = root;
        for(int i=0;i<prefix.length();i++){
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }
        return true;
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        String word = "aple";
        obj.insert(word);
        boolean param_2 = obj.contains("apl");
//        System.out.println(obj.size);
        System.out.println(param_2);
//        boolean param_3 = obj.isPrefix(prefix);
    }
}
